package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.ListNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 23. 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 * <p>
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：lists = [[]]
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 */
public class Lc23 {

    public static void main(String[] args) {
//        List<String> strings = generateParenthesis2(2);
//        System.out.println(strings);
        ListNode node0 = new ListNode();
        ListNode node00 = new ListNode();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        Deque<ListNode> nodeDeque = new ArrayDeque<>();
        HashSet<ListNode> nodeSet = new HashSet<>();
        nodeSet.add(node0);
        nodeSet.add(node00);
        nodeDeque.addLast(node0);
        nodeDeque.addLast(node1);
        nodeDeque.addLast(node2);
        System.out.println(nodeDeque);
        System.out.println(nodeDeque.peek());
        System.out.println(nodeDeque);
        for (ListNode node : nodeDeque) {
            System.out.println(node);
        }
        System.out.println(nodeSet);
        System.out.println(Integer.MIN_VALUE);

    }


    static List<String> list = new LinkedList();

    /**
     * 暴力法：<br>
     * 全部加入list，再排序，再挨个链接
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        ArrayList<ListNode> listNodes = new ArrayList<>();
        for (ListNode listNode : lists) {
            while (listNode != null) {
                listNodes.add(listNode);
                listNode = listNode.next;
            }
        }
        List<ListNode> collect = listNodes.stream().sorted(Comparator.comparingInt(n -> n.val)).collect(Collectors.toList());
        ListNode head = new ListNode();
        ListNode pointer = head;
        for (ListNode node : collect) {
            pointer.next = node;
            pointer = pointer.next;

        }
        return head.next;
    }

    /**
     * 两两合并法
     * 取一个ans链表，挨个从数组中取一个和ans两两合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        //根据条件，可能有空链表
        if (p1 == null || p2 == null) {
            return p1 != null ? p1 : p2;
        }
        ListNode head = new ListNode(0);
        //指针记位
        ListNode temp = head, p1Pointer = p1, p2Pointer = p2;
        while (p1Pointer != null && p2Pointer != null) {
            if (p1Pointer.val < p2Pointer.val) {
                temp.next = p1Pointer;
                p1Pointer = p1Pointer.next;
            } else {
                temp.next = p2Pointer;
                p2Pointer = p2Pointer.next;
            }
            temp = temp.next;
        }
        temp.next = (p1Pointer != null ? p1Pointer : p2Pointer);
        return head.next;
    }
}
